#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

def avl_least_num(depth):
    # 空节点高度为-1
    # 单节点高度为0
    if depth in [0, 1]:
        return depth + 1

    # for i in range
    first_cnt, second_cnt = 1, 2

    for dep in range(2, depth+1):
        first_cnt, second_cnt = second_cnt, first_cnt + second_cnt + 1
    return second_cnt

def test_avl_least_num():
    assert avl_least_num(9) == 143
    print(avl_least_num(7))
    print(avl_least_num(8))
    print(avl_least_num(9))
    print(avl_least_num(15))
    # 370959230771131880927453318055001997489772178180790103
    print(avl_least_num(255))       # 255高度可以存储很多的node, 所以avl节点如果需要depth field, char8是很够用的.

def avl_vs_complete():
    for i in range(50):
        complete = 2 ** (i+1) - 1
        avl = avl_least_num(i)
        print('depth %s: cmp %s' % (i, complete / avl))

def main():
    print("start main")
    # test_avl_least_num()
    avl_vs_complete()

if __name__ == "__main__":
    main()
